package com.linyaonan.leetcode.medium._633;

/**
 * 给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：c = 5
 * 输出：true
 * 解释：1 * 1 + 2 * 2 = 5
 * 示例 2：
 *
 * 输入：c = 3
 * 输出：false
 *  
 *
 * 提示：
 *
 * 0 <= c <= 2^31 - 1
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/sum-of-square-numbers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {
    public boolean judgeSquareSum(int c) {
        if (c == 0 || c == 1) {
            return true;
        }

        int h = c >> 1;
        int sh = (int) Math.sqrt(h);

        for (int i = 0; i <= sh; i++) {
            if (hasZ(c - (i * i))) {
                return true;
            }
        }

        return false;
    }

    /**
     * 校验该值是否可以由平方得来
     * @param p
     * @return
     */
    private boolean hasZ(int p) {
        int l = 0;
        int r = 46340;

        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (mid > p) {
                r = mid - 1;
                continue;
            }
            int z = mid * mid;
            if (z == p) {
                return true;
            }
            if (z < p) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return false;
    }
}